package 剑指offer_专项突破版;

/**
 * 剑指 Offer II 075. 数组相对排序
 */
public class Num75 {
    //计数排序
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        //定义存储数据个数的数组xounts
        int[] counts = new int[1001];
        //存arr1的数据个数
        for (int num : arr1){
            counts[num] ++;
        }
        int i = 0;
        //先找到arr2的数组元素进行存储
        for (int num : arr2){
            while (counts[num] > 0){
                arr1[i++] = num;
                counts[num] --;
            }
        }
        //余下的数据继续向后存储
        for (int num = 0; num < counts.length; num++) {
            while (counts[num] > 0){
                arr1[i++] = num;
                counts[num] --;
            }
        }
        //不用开辟额外数组，直接改变arr1的顺序返回
        return arr1;
    }
}
